package com.dataStructure.leetcode.栈;

import java.util.HashMap;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/valid-parentheses/
 */
public class 有效的括号 {

    public  static boolean isValid(String s) {
        int len = s.length();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            //获取某一个位置的字符
            char c = s.charAt(i);
            //字符用的是单引号
            if (c == '{' || c == '['|| c =='('){
                stack.push(c);
            }else {
                if (stack.isEmpty())return false;
                char left = stack.pop();
                if (left == '{' && c !='}')return  false;
                if (left == '[' && c !=']')return  false;
                if (left == '(' && c !=')')return  false;
            }
        }
        return stack.isEmpty();
    }


    public  static boolean isValid1(String s) {
        //效率低
        while (s.contains("{}" )|| s.contains("[]")|| s.contains("()")){
            s = s.replace("{}","");
            s = s.replace("()","");
            s = s.replace("[]","");
        }
        return s.length() == 0;
    }

    //这个算法有很多映射关系，应该考虑到使用map来解决
    private  HashMap<Character,Character> map = new HashMap<>();

    public 有效的括号(){
        map.put('{','}');
        map.put('[',']');
        map.put('(',')');
    }

    public  boolean isValid3(String s) {
        int len = s.length();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            //获取某一个位置的字符
            char c = s.charAt(i);
            //字符用的是单引号
            if (map.containsKey(c)){
                stack.push(c);
            }else {
                if (stack.isEmpty())return false;

                char left = stack.pop();
                if (c != map.get(left))return false;
            }
        }
        return stack.isEmpty();
    }


    public static void main(String[] args) {

    }
}
